package sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class HeapSort {

    /**
     * 选择排序-堆排序-不稳定排序
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr){
        if(arr == null || arr.length <= 1){
            return;
        }

        //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
        for(int i= arr.length/2-1; i>=0; i--){
            adjustHeap(arr, i, arr.length); // 调整堆
        }

        // 上述逻辑，建堆结束
        // 下面，开始排序逻辑
        for(int j = arr.length-1; j>0; j--){
            // 元素交换，作用是去掉大顶堆
            // 把大顶堆的根元素，放到数组的最后；
            // 换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
            swap(arr, 0, j);
            adjustHeap(arr, 0, j);
        }
    }

    /**
     * 整个堆排序最关键的地方
     * @param arr 待组堆
     * @param i 起始结点
     * @param length 堆的长度
     */
    public static void adjustHeap(int[] arr, int i, int length){
        // 先把当前元素取出来，因为当前元素可能要一直移动
        int temp = arr[i];
        // 2*i+1 为i的左子树
        // 2*k+1 为k的左子树
        for(int k = 2 * i + 1; k < length; k = 2 * k + 1){
            // 让 k 先指向子节点中最大的节点
            if(k+1 < length && arr[k] < arr[k+1]){  // 如果有右子树，并且右子树大于左子树
                k++;
            }
            // 如果发现节点（左右子节点）大于根节点，则进行值的交换
            if(arr[k] > temp){
                swap(arr, i, k);
                i = k;
            } else {
                break;
            }
        }
    }

    public static void swap(int[] arr, int i, int j){
        if( i == j){
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
        heapSort(arr);
        System.out.println(Arrays.stream(arr).boxed().collect(Collectors.toList()));
    }
}
